package entity;

/**
 * @Author: wanqian
 * @Date: 2021/2/4 15:11
 */
public class BinaryTree {

    private TreeNode head;

    private TreeNode preNode;

    public BinaryTree() {
    }

    public BinaryTree(TreeNode head) {
        this.head = head;
    }

    /**
     * 后序线索化
     */
    public void postThreadedNode() {
        if (head != null) {
            this.postThreadedNodes(head);
        } else {
            System.out.println("二叉树为空");
        }
    }

    public int height() {
        if (head == null) {
            return 0;
        }
        return height(head);
    }

    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height(node.getLeft()), height(node.getRight())) + 1;
    }

    /**
     * 、
     * 后续线索化
     *
     * @param treeNode
     */
    public void postThreadedNodes(TreeNode treeNode) {

        //向左节点遍历
        if (treeNode.getLeft() != null) {
            postThreadedNodes(treeNode.getLeft());
        }

        //向右节点遍历
        if (treeNode.getRight() != null) {
            postThreadedNodes(treeNode.getRight());
        }//没有右节点时，要用右指针指向下个节点，需要等待下个节点进行

        //处理当前节点
        if (treeNode.getLeft() == null) {
            treeNode.setLeft(preNode);
            treeNode.setLeftType(1);
        }
        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(treeNode);
            preNode.setRightType(1);
        }
        preNode = treeNode;
    }

    /**
     * 后续线索化遍历
     */
    public void postThreadedList() {
        if (head == null) {
            System.out.println("二叉树为空!");
            return;
        }
        postThreadedList(head);
    }

    /**
     * 后续线索化遍历
     * 实现效果不好，仅根据遇到的问题做了相应规避（有时间再研究）
     *
     * @param treeNode
     */
    private void postThreadedList(TreeNode treeNode) {
        //若有左节点则递归
        if (treeNode.getLeft() != null && treeNode.getLeftType() == 0) {
            postThreadedList(treeNode.getLeft());
        } else {
            //没有则输出当前节点
            System.out.println(treeNode);
        }

        //根据右线索开始逐个打印
        TreeNode temp = treeNode;
        while (temp.getRight() != null && temp.getRightType() == 1) {
            temp = temp.getRight();
            System.out.println(temp);
        }

        if (treeNode.getRight() != null && treeNode.getRightType() == 0) {
            if (treeNode != treeNode.getRight().getRight()) {
                postThreadedList(treeNode.getRight());
            }
        }

        //往左递归的节点最后打印自己
        if (treeNode.getLeft() != null && treeNode.getLeftType() == 0) {
            if (treeNode != treeNode.getRight().getRight()) {
                System.out.println(treeNode);
            }
        }
    }

    /**
     * 前序线索化
     */
    public void preThreadedNodes() {
        if (head != null) {
            this.preThreadedNodes(head);
        } else {
            System.out.println("二叉树为空");
        }
    }

    /**
     * 前序线索化
     *
     * @param treeNode
     */
    public void preThreadedNodes(TreeNode treeNode) {

        //处理当前节点
        if (treeNode.getLeft() == null) {
            treeNode.setLeft(preNode);
            treeNode.setLeftType(1);
        }
        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(treeNode);
            preNode.setRightType(1);
        }
        preNode = treeNode;

        //向左节点遍历
        if (treeNode.getLeft() != null && treeNode.getLeftType() == 0) {
            preThreadedNodes(treeNode.getLeft());
        }

        //向右节点遍历
        if (treeNode.getRight() != null) {
            preThreadedNodes(treeNode.getRight());
        }//没有右节点时，要用右指针指向下个节点，需要等待下个节点进行
    }

    public void preThreadedList() {
        if (head == null) {
            System.out.println("二叉树为空!");
            return;
        }

        TreeNode temp = head;
        System.out.println(temp);
        while (temp != null) {
            //找到最左侧的节点
            while (temp.getLeftType() != 1) {
                temp = temp.getLeft();
                System.out.println(temp);
            }

            //通过右线索遍历，直到遇到一个有右节点的节点
            while (temp.getRightType() == 1) {
                temp = temp.getRight();
                System.out.println(temp);
            }

            if (temp.getRight() == null) {
                break;
            }
        }
    }

    /**
     * 中序线索化
     */
    public void infixThreadedNodes() {
        if (head != null) {
            this.infixThreadedNodes(head);
        } else {
            System.out.println("二叉树为空");
        }
    }

    /**
     * 中序线索化
     *
     * @param treeNode
     */
    public void infixThreadedNodes(TreeNode treeNode) {

        //向左节点遍历
        if (treeNode.getLeft() != null) {
            infixThreadedNodes(treeNode.getLeft());
        }

        //处理当前节点
        //向左进行线索化
        if (treeNode.getLeft() == null) {
            treeNode.setLeft(preNode);
            treeNode.setLeftType(1);
        }
        //让上一个节点线索指向当前节点
        if (preNode != null && preNode.getRight() == null) {
            preNode.setRight(treeNode);
            preNode.setRightType(1);
        }
        //记录当前节点为上一个节点
        preNode = treeNode;

        //向右节点遍历
        if (treeNode.getRight() != null) {
            infixThreadedNodes(treeNode.getRight());
        }//没有右节点时，要用右指针指向下个节点，需要等待下个节点进行
    }

    /**
     * 中序线索遍历
     */
    public void infixThreadedList() {
        if (head == null) {
            System.out.println("二叉树为空!");
            return;
        }

        TreeNode temp = head;
        while (temp != null) {
            //找到最左侧的节点
            while (temp.getLeftType() != 1) {
                temp = temp.getLeft();
            }

            System.out.println(temp);
            //通过右线索遍历，直到遇到一个有右节点的节点
            while (temp.getRightType() == 1) {
                temp = temp.getRight();
                System.out.println(temp);
            }
            temp = temp.getRight();
        }
    }

    public void preOrder() {
        if (head != null) {
            this.head.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public TreeNode preOrderSearch(int id) {
        if (head != null) {
            return this.head.preOrderSearch(id);
        } else {
            return null;
        }
    }

    public void infixOrder() {
        if (head != null) {
            this.head.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public TreeNode infixOrderSearch(int id) {
        if (head != null) {
            return this.head.infixOrderSearch(id);
        } else {
            return null;
        }
    }

    public void postOrder() {
        if (head != null) {
            this.head.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }

    public TreeNode postOrderSearch(int id) {
        if (head != null) {
            return this.head.postOrderSearch(id);
        } else {
            return null;
        }
    }

    public void deleteById(int id) {

        if (head == null) {
            System.out.println("二叉树为空");
        }

        if (head.getId() == id) {
            head = null;
        }

        this.head.deleteById(id);
    }

    public TreeNode getHead() {
        return head;
    }

    public void setHead(TreeNode head) {
        this.head = head;
    }
}
